package fun.coding.string;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

//import org.apache.log4j.Logger;

public class StringManipulationImpl implements StringManipulation {
	
//	private static final Logger logger = Logger.getLogger(StringManipulation.class);
	
    /**
     * For example, s = "banana" -> b, basically build a hashmap and loop through the array again 
     */
	@Override
	public char findFirstNonRepeatedChar(String s) {
		Map<Character, Boolean> charOccurrenceMap = new HashMap<Character, Boolean>();
		
		for(int i = 0; i < s.length(); i++) {
			if(charOccurrenceMap.containsKey(s.charAt(i))) {
				charOccurrenceMap.put(s.charAt(i), false);
			} else {
				charOccurrenceMap.put(s.charAt(i), true);
			}
		}
		
		for(int i = 0; i < s.length(); i++ ) {
			if(charOccurrenceMap.get(s.charAt(i))) {
				return s.charAt(i);
			}
		}
		
		return 0;
	}
	
	/**
	 * This is the same as removing a certain number in an array. O(N) with no extra space.
	 */
	@Override
	public String removeString(String src, String remove) {
		Collection<Character> c = new ArrayList<Character>();
		
		for(int i = 0; i < remove.length(); i++) {
			c.add(remove.charAt(i));
		}
		
		for(Character it : c) {
			//System.out.println(it);
	//		logger.info(it);
		}
		
		for(int i = 0; i < src.length(); i++) {
			if(c.contains(src.charAt(i))) {
				System.out.println(src.charAt(i));
				src = src.replace(src.charAt(i), '\0');
			}
		}
		
		return src;
		
	}
	// Tony suggested on method that reverse string and do it again. 
	// good day -> yad doog -> day good 
	// have a good day -> day good a have
	public String revertString(String s) {
		String[] ss = s.split(" ");
		// use StringBuilder (for single thread only, asynchronized, thus slightly faster than StringBuffer)
		// definitely faster than ss += s since it creates a new object every time.
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = ss.length - 1; i >= 0; i--) {
			sb.append(ss[i]);
			sb.append(" ");
		}
		
		return sb.toString();
	}

	// have a good day -> yad doog a evah
	@Override
	public String revertStringWord(String s) {
		Stack<Character> stack = new Stack<Character>();
		for(int i = 0; i < s.length(); i++) {
			stack.push(s.charAt(i));
		}
		
		StringBuilder sb = new StringBuilder();
		
		while(!stack.isEmpty()) {
			sb.append(stack.pop());
		}
		
		return sb.toString();
	}

	/**
	 * Assume s1 always contain s2, 
	 * "abc" "ab", print 2
	 * "abc", "b", print 0, 2
	 * "abc", "", print 0, 1, 2
	 * abc, ac, print 1
	 * aab, ab could either print 0 or 1
	 */
    @Override
    public void printDiffPositionBetweenTwoStrings(String s1, String s2) {
 
        int j = 0;
        for(int i = 0; i < s1.length(); i++) {
            if(j >= s2.length() || s1.charAt(i) != s2.charAt(j)) {
                System.out.println(i);
            } else {
                j++;
            }
        }
        
    }

    /*
     * Find all the anagrams within the given array. An anagram is the string with all the same number of chars.
     * For example, tea, ate, eat
     * The trick part is to use 2 hashmaps to use the unique chars and numbers as a key so that it is O(N).
     * 
     */
	@Override
	public ArrayList<String> anagrams(String[] strs) {
		Map<String, HashMap<Character, Integer>> map = new HashMap<String, HashMap<Character, Integer>>();
		Map<HashMap<Character, Integer>, Integer> countMap = new HashMap<HashMap<Character,Integer>, Integer>();
		
		for(String s : strs) {
			HashMap<Character, Integer> m = new HashMap<Character, Integer>();
			
			for(int i = 0; i < s.length(); ++i) {
				char c = s.charAt(i);
				m.put(c, (m.get(c) == null) ? 1 : m.get(c) + 1);
			}
			
			map.put(s, m);
			
			countMap.put(m, (countMap.get(m) == null) ? 1 : countMap.get(m) + 1);
		}
		
		ArrayList<String> result = new ArrayList<String>();
		
		for(String str : strs) {
			if(countMap.get(map.get(str)) > 1) {
				result.add(str);
			}
		}
		
		
		return result;
	}

	/*
	 * This is basically the C++ implementation of strStr(), returns the first occurrence of a string or null if not exist
	 * Example, abcdcdef, cde => cdef 
	 */
	@Override
	public String strStr(String haystack, String needle) {
		if(haystack.length() < needle.length())
			return null;
		
		if(needle.length() == 0)
			return haystack;
		
		// We don't need to compare the part the length is shorter than needle.
		// The difference between strings. 
		int diff = haystack.length() - needle.length() + 1;
		
		// Basically just use substring and start with. 
		for(int i = 0; i < diff; ++i) {
			if(haystack.substring(i).startsWith(needle))
				return haystack.substring(i);
		}
		
		return null;
	}

	/* This is a very elegant C solution.
	 * For example, "have a good day " => "haveagoodday"
	 * require O(N) with no extra space
	 */
    @Override
    public String removeSpaceFromString(String s) {
        char[] charArray = s.toCharArray();
        int i = 0; 
        int j = 0;

        // TODO: use this to rewrite condense number.
        while(j < s.length()) {
            // saves just a little bit efficiency. 
            if(i != j ) {
                charArray[i] = charArray[j];
            }
            
            if(charArray[j] == ' ') {
                j++;
            } else {
                i++;
                j++;
            }
        }
        
//        for(int k = 0; k < i; ++k) {
//            System.out.println(charArray[k]);
//        }
        
        return new String(charArray, 0, i-1);
    }

    /* For example, aabcccdd => abcd
     * The idea is just to keep two pointers, and compare with a previous value. 
     * If the string is not ordered, e.g, abcaabbcc, use a hashset will solve it. 
     * */
    @Override
    public String removeDuplicateOrdered(String s) {
        if(s == null)
            return null;
        
        if(s.length() <= 1)
            return s;
        
        int i = 1, j = 1;
        
        char[] ss = s.toCharArray();
        char pre = ss[0];
        
        while(j < ss.length) {
            if(pre == ss[j]) {
                j++;
            } else {
                ss[i] = ss[j];
                pre = ss[j];
                j++;
                i++;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(int k = 0; k < i; ++k) {
            sb.append(ss[k]);
        }
        
        return sb.toString();
    }
    
    
    /*
     * 199 + 20 = 219
     * 900 + 200 = 1100
     * 801 + 110 = 911
     * (non-Javadoc)
     * @see interview.coding.string.StringManipulation#addTwoStrings(java.lang.String, java.lang.String)
     */
	@Override
	public String addTwoStrings(String s1, String s2) {
		int maxLength = Math.max(s1.length(), s2.length());
		int count = 0;
		int i = s1.length() - 1;
		int j = s2.length() - 1;
		
		int carry = 0;
		StringBuilder sb = new StringBuilder();
		
		while(i >= 0 && j >= 0) {
			carry = addTwoDigits(s1.charAt(i), s2.charAt(j), carry, sb); 
			
			i--;
			j--;
		}
		
		while(i >= 0) {
			carry = addTwoDigits(s1.charAt(i), '0', carry, sb);
			i--;
		}
		
		while(j >= 0) {
			carry = addTwoDigits('0', s2.charAt(j), carry, sb);
			j--;
		}
		
		if(carry != 0) {
			sb.append(carry);
		}
		
		return sb.toString();
	}

	private int addTwoDigits(char c1, char c2, int carry, StringBuilder sb) {
		int total = Integer.parseInt(Character.toString(c1)) + Integer.parseInt(Character.toString(c2)) + carry;
		int res = total % 10;
		carry = total / 10;
		sb.append(res);
		
		return carry;
	}

	/*
	 * for example, abc will return 8 results, 
	 * {}, a, b, c, ab, ac, bc, abc,
	 * 
	 * The idea is using bitmask, 2^n, do it iteratively. 
	 * */
    @Override
    public ArrayList<String> findAllSubSets(String s) {
        ArrayList<String> l = new ArrayList<String>();
        
        for(int i = 0; i < 1 << s.length(); ++i) {
            StringBuilder sb = new StringBuilder();
            
            for(int j = 0; j < s.length(); ++j) {
                if(((i >> j) & 1) == 1) {
                    sb.append(s.charAt(j));
                }
            }
            l.add(sb.toString());
        }
        
        
        return l;
    }

    /*
     * I don't need 2 hashmap to fulfil this, build a hashmap from s1, and then reduce it from s2.
     * Instead of hashmap, i could use a int[256] to recode the value. 
     * */
    public static final int MAX_CHAR = 256;
    @Override
    public boolean isSameCharSet(String s1, String s2) {
        if(s1.length() != s2.length())
            return false;
        
        int[] map = new int[MAX_CHAR];
        
        for(int i = 0; i < s1.length(); ++i) {
            map[Character.getNumericValue(s1.charAt(i))]++;
        }

        for(int i = 0; i < s2.length(); ++i) {
            if(--map[Character.getNumericValue(s2.charAt(i))] < 0) {
                return false;
            }
        }
        
        return true;
    }

    /* Asked by a SDEIII at Amazon
     * 10.10.10.1 -> remove dots -> 1010101 -> how many valid ip address can it generate?
     * */
    @Override
   
    public ArrayList<String> parseIPNoDot(String ip) {
        ArrayList<String> res = new ArrayList<String>();
        // validation check goes first and should've thrown exceptions
        if(ip.length() < 4 || ip.length() > 12) {
            // return empty array instead of null.
            return res;
        }
        //http://heartfire.cc/wp/restore-ip-addresses/
        // This is really a simple idea, should've come up with this solution!!
        //TODO: there is a recursion solution. 
        for(int i = 1; i < ip.length(); ++i) {
            for(int j = i + 1; j < ip.length(); ++j) {
                for(int k = j + 1; k < ip.length(); ++k) {
                    if(isValidIp(ip.substring(0, i)) 
                            && isValidIp(ip.substring(i, j)) 
                            && isValidIp(ip.substring(j, k)) 
                            && isValidIp(ip.substring(k, ip.length()))) {
                        res.add(ip.substring(0, i) + "." + ip.substring(i, j) + "." + ip.substring(j, k) + "." + ip.substring(k, ip.length()));
                    }
                }
            }
        }
        
        
        
        // FIXME: this is what the SDEIII told, i don't really understand and like it, 
        // there is a more straightforward way to brute force
        /* 
        for(int i = 0; i < 3; ++i) {
            for(int j = 0; j < ip.length(); ++j) {
               StringBuilder sb = new StringBuilder();
               for(int k = j; k < j + 3; ++k) {
                   if(k < ip.length()) {
                       sb.append(ip.charAt(k));
                   }
               }
               if(isValidIp(sb.toString())) {
                   res.add(sb.toString() + ".");
               }
            }
            
        }
        */
        
        return res;
    }
    
    // 255.255.255.255 
    private boolean isValidIp(String s) {
        //1.010.0.1 using this simple way would result in such a case
        return Integer.parseInt(s) > 255 ? false : true;
    }

    @Override
    public ArrayList<String> parseIPNoDotRecursive(String ip) {
         //TODO Auto-generated method stub
        return null;
    }

    /* Hulu interview question
     * abba is a palindrome
     * a. is
     * .a is
     * a#ba is true
     * Aba is true
     * Basically it needs to know whether it is a char or not. 
     * */
	@Override
	public boolean isPalindrome(String s) {
		if(s == null || s.isEmpty() || s.length() == 1)
			return true;
		
		// need to consider the case diff
		s = s.toLowerCase();
		
		int i = 0; 
		int j = s.length() - 1;
		
		while(i < j) {
			if(!isLetter(s.charAt(i))) {
				i++;
			} else if(!isLetter(s.charAt(j))) {
				j--;
			} else {
				if(s.charAt(i++) != s.charAt(j--)) { 
					return false;
				}
			}
		}
		
		return true;
	}
	
	private boolean isLetter(char c){
		if(c >= 'a' && c <= 'z' || (c >= '0' && c <= '9'))
			return true;
		else 
			return false;
	}

	/* This is Shawn's google phone interview
	 * local = l3l
	 * abc = a1c
	 * a invalid
	 * ab a0b
	 * 
	 * Given a string array of words, determine if the target string is in the array or not. 
	 * 
	 * For example, String[] = {abcd, abbd, abc} target abc is in there and only exists once
	 * */
	@Override
	public boolean isEncodedStringExist(String[] s, String target) {
		HashMap<String, Integer> map = new HashMap<String, Integer>();
		for(String ss : s) {
			try {
				String key = encode(ss);
				map.put(key, map.containsKey(key) ? map.get(key) + 1 : 1);
			} catch(Exception e) {
				// do nothing
			}
		}
		
		return map.get(encode(target)) == 1 ? true : false;
	}
	
	public String encode(String s) {
		/*
		if(s == null || s.length() == 1) { 
			throw new Exception("invalid input");
		}
		*/
		String newS = Character.toString(s.charAt(0)) + (s.length() - 2) + Character.toString(s.charAt(s.length() - 1));
		return newS;
	}

	/* 
	 * http://leetcode.com/onlinejudge#question_5
	 * abcbab will return abcba
	 * Brute force one will have O(N^3) since determine palindrome is O(N) and there are C(N,2) positions for start
	 * and end point. (but this is too stupid though)
	 * 
	 * The catch here is using palindrome is symmetric and we could expand from the centers. 
	 * There are two cases for odd and even number, aa center is in the middle aba cener is b.
	 * This is O(N^2)
	 * 
	 * */
    @Override
    public String longestPalindrome(String s) {
        if(s == null)
            return null;
        if(s.length() <= 1)
            return s;
        
        String longestPali = "";
        for(int i = 0; i < s.length(); ++i) {
            String partialOdd = getLongestPalindrome(s, i, i + 1);
            if(partialOdd.length() > longestPali.length()) {
                longestPali = partialOdd;
            }
            
            String partialEven = getLongestPalindrome(s, i, i);
            if(partialEven.length() > longestPali.length()) {
                longestPali = partialEven;
            }
        }
        
        return longestPali;
    }
    
    private String getLongestPalindrome(String s, int l, int r) {
        String result = "";
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            result = s.substring(l, r + 1);
            l--;
            r++;
        }
        
        return result;
    }

    /* TODO:  white guy on Microsoft's question. 
     * fooddog dog return 4
     * 
     * I implemented one with bug that is fofoodog foo will skip that f.
     * Feel humiliated implementing a buggy O(N^2). 
     * 
     * 2nd question distinguish a devI between a devII
     * define different methods for different sorting. 
     * 
     * requirements:
     * fooddog
     * f - 1
     * o - 3
     * d - 2
     * g - 3
     * should implement the code in a way that can have different orders by letter or by count, future maintainable
     * have different components, parser that parses the data and displayer that display the data. 
     * */
    @Override
    public int findFirstMatchingWord(String s, String p) {
        return 0;
    }

    /* Micrsoft question, i divided the number and looked it up each chars.
     * TODO: google it for a better solution.
     * And this guys Jason directly pointed out that I made some mistakes about our kiva sevice, we do use 
     * distributed locking, LDS, since the lease is not partitioned, so currently there will be only 1 thread.
     * If this thread dies, another host's thread could be waken up and grab the lease. if we want to enable multiple theads,
     * we need to have a partition key, like INS does.  
     * */
    @Override
    public String intToString(int n) {
        return null;
    }

}
